package src.leetcode.backtrack.medium_0039;

import java.util.ArrayList;
import java.util.List;

public class combinationSum {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.combinationSum(new int[]{2,3,6,7}, 7));
    }
}


class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    int[] candidates;
    int target;
    ArrayList<Integer> nums = new ArrayList<>();
    int sum = 0;
    int index = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        this.target = target;
        backtrack();
        return ans;
    }

    private void backtrack() {
        if(sum > target) return;
        if(sum == target) ans.add(new ArrayList<>(nums));
        for(int i = index; i < candidates.length; i++){
            sum += candidates[i];
            nums.add(candidates[i]);
            index = i;
            backtrack();
            nums.remove(nums.size() - 1);
            sum -= candidates[i];
        }
    }
}